package fun.coding.tree.bst;

import java.util.ArrayList;

import fun.coding.leetcode.TreeNode;

public class LowestCommonAncestor {

    /**
     * http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html
     * Use post order traversal 
     * 
     *  _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4
     * 
     */
    public static void main(String[] args) {
        ArrayList<TreeNode> nodeList = new ArrayList<TreeNode>();
        constructTree(nodeList);
        // inorderTraversal(nodeList.get(3));
        TreeNode lca = lowestCommonAncestor(nodeList.get(3), nodeList.get(7), nodeList.get(8));
        System.out.println("LCA is " + lca.val);
    }
    
    public static void constructTree(ArrayList<TreeNode> nodeList) {
        for (int i = 0; i < 9; i++) {
            TreeNode n = new TreeNode(i);
            nodeList.add(n);
        }
        
        nodeList.get(2).left = nodeList.get(7);
        nodeList.get(2).right = nodeList.get(4);
        
        nodeList.get(5).right = nodeList.get(2);
        nodeList.get(5).left = nodeList.get(6);
        
        nodeList.get(1).right = nodeList.get(8);
        nodeList.get(1).left = nodeList.get(0);
        
        nodeList.get(3).right = nodeList.get(1);
        nodeList.get(3).left = nodeList.get(5);
    }
    
    public static void inorderTraversal(TreeNode root) {
        if (root == null) return;
        
        inorderTraversal(root.left);
        System.out.print(root.val + ", ");
        inorderTraversal(root.right);
    }
    
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        
        if (root == p || root == q) return root;
        
        // Post order traveral
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        
        if (l != null && r != null) {
            return root;
        } else {
            return l != null ? l : r;
        }
    }
    
}
